class Solution {
public:
    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */
    // 序列型动态规划+状态
    // 状态的设计：需要知道油漆前N-1栋房子的最优策略中，房子N-2的颜色。如果只用f[N-1], 将无法区分
    int minCost(vector<vector<int>> &costs) {
        if (costs.empty()) return 0;
        int n = costs.size();
        int types = costs[0].size();
        int res = INT_MAX;
        vector<vector<int>> rec(n, vector<int>(types));
        for (int i = 0; i < types; ++i) {
            rec[0][i] = costs[0][i];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < types; ++j) {
                // rec[i][j] = min(rec[i - 1][(j - 1) % 3], rec[i - 1][(j - 2) % 3]) + costs[i][j]; 这边的余数就是负数
                rec[i][j] = min(rec[i - 1][(j + 1) % 3], rec[i - 1][(j + 2) % 3]) + costs[i][j];
            }
        }
        for (int i = 0; i < types; ++i) {
            res = min(res, rec[n - 1][i]);
        }
        return res;
    }
};